package com.agile.leetcode.array.miss;

/**
 * 接雨水问题
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 * 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
 *
 * 示例:
 *
 * 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出:
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PickRain {
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int sUm = getSUm(arr);
        int height[] = {4, 2, 0, 3, 2, 5};
        System.out.println(sUm);
        System.out.println(getResult(height));
        System.out.println(dynamic(height));
    }

    /**
     * 单独计算每列
     * 取出每列的左边和右边元素的最大值，并且每列的值在左边右边最大值的中间
     * min(leftMax,rightMax)-arr[i]的累加即为所接雨水的面积
     *
     * @param arr
     * @return
     */
    public static int getSUm(int[] arr) {
        int len = arr.length;
        int leftMax = 0;
        int rightMaX = 0;
        int sum = 0;
        for (int i = 1; i < len - 1; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > leftMax) leftMax = arr[j];
            }
            for (int j = i + 1; j < len; j++) {
                if (arr[j] > rightMaX) rightMaX = arr[j];
            }
            if (arr[i] < leftMax && arr[i] < rightMaX) {
                sum += Math.min(leftMax, rightMaX) - arr[i];
                leftMax = 0;
                rightMaX = 0;
            }
        }
        return sum;
    }

    /**
     * 暴力解法
     *
     * @param arr
     * @return
     */
    public static int getResult(int[] arr) {
        int max = 0;
        for (int i = 1; i < arr.length; i++) {
            int leftMax = 0;
            int rightMax = 0;
            // 左边最大值
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, arr[j]);
            }
            // 右边最大值
            for (int j = i; j <= arr.length - 1; j++) {
                rightMax = Math.max(rightMax, arr[j]);
            }
            max += Math.min(leftMax, rightMax) - arr[i];
        }
        return max;
    }

    /**'
     * 动态规划
     *
     * @param arr
     * @return
     */
    public static int dynamic(int[] arr) {
        int length = arr.length;
        int[] leftMax = new int[length];
        int[] rightMax = new int[length];
        leftMax[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            leftMax[i] = Math.max(arr[i], leftMax[i-1]);
        }
        rightMax[length - 1] = arr[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(arr[i], rightMax[i + 1]);
        }
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            max = Math.min(leftMax[i], rightMax[i]) - arr[i] + max;
        }
        return max;
    }
}
